Abstract-The -ary -cube is one of the most important interconnection networks for building network-on-chips, data center networks, and parallel computing systems owing to its desirable properties. Since edge faults grow rapidly and the path structure plays a vital role in large-scale networks for parallel computing, fault-tolerant path embedding and its related problems have attracted extensive attention in the literature. However, the existing path embedding approaches usually only focus on the theoretical proofs and produce an -related linear fault tolerance since they are based on the traditional fault model, which allows all faults to be adjacent to the same node. In this paper, we design an efficient fault-tolerant Hamiltonian path embedding algorithm for enhancing the fault-tolerant capacity of -ary -cubes. To facilitate the algorithm, we first introduce a new conditional fault model, named Partitioned Edge Fault model (PEF model). Based on this model,for the -ary -cube with and odd ,we explore the existence of a Hamiltonian path in with large-scale edge faults. Then we give an algorithm,named HP-PEF, to embed the Hamiltonian path into under the PEF model, where is the number of nodes in . The performance analysis of HP-PEF shows the average path length of adjacent node pairs in the Hamiltonian path constructed by HP-PEF. We also make comparisons to show that our result of edge fault tolerance has exponentially improved other known results. We further experimentally show that HP-PEF can support the dynamic degradation of average success rate of constructing Hamiltonian paths when increasing faulty edges exceed the fault tolerance.
摘要- -元 -立方体 是构建网络芯片、数据中心网络和并行计算系统最重要的互联网络之一,这要归功于其理想的特性。由于边缘故障迅速增长,并且在并行计算的大规模网络中路径结构发挥着至关重要的作用,因此在文献中,容错路径嵌入及其相关问题已经引起了广泛的关注。然而,现有的路径嵌入方法通常只关注理论证明,并且由于它们基于传统的故障模型,该模型允许所有故障与同一节点相邻,因此它们产生了与 相关的线性故障容忍度。在本文中,我们设计了一种高效的容错哈密顿路径嵌入算法,以提高 -元 -立方体的故障容忍能力。为了便于算法的实现,我们首先引入了一种新的条件故障模型,名为分区边缘故障模型(PEF模型)。基于这个模型,对于具有 和奇数 的 -元 -立方体 ,我们探讨了在存在大规模边缘故障的 中哈密顿路径的存在性。然后我们给出了一种名为HP-PEF的算法,用于在PEF模型下将哈密顿路径嵌入到 中,其中 是 中的节点数。HP-PEF的性能分析显示了由HP-PEF构建的哈密顿路径中相邻节点对的平均路径长度。我们还进行了比较以显示我们的边缘故障容忍结果指数级地优于其他已知结果。我们进一步通过实验表明,当增加的故障边超过故障容忍度时,HP-PEF可以支持构建哈密顿路径的平均成功率动态下降。